The Invisible Power of Mathematics by Giovanni Samaey & Joos P. L. Vandewalle

Author:Giovanni Samaey & Joos P. L. Vandewalle
Language: eng
Format: epub
ISBN: 9781071627761
Publisher: Springer US

The P versus NP problem

Problems come in different shapes and sizes. For convenience, we stick labels on them. Problems in category ‘P’ are problems for which a ‘fast’ solution method exists: the necessary calculation time for a fast solution method is proportional to a power of the number of unknowns. For problems in category ‘NP’ we can ‘quickly’ check the correctness of proposed solutions. Checking a solution is often easier than finding a solution: for example, it requires less work to see if a row is sorted than to actually sort a row.

We know the bicycle sharing problem is in the category ‘NP’: here checking the optimality of a solution is relatively simple, but finding the optimal solution is very difficult – and this purely because there are so many possible solutions. Of course all ‘P’ problems are also ‘NP’. But is the converse also true? If you look at the bicycle sharing problem, you would think it isn’t. We only have at our disposal ‘slow’ solution methods for the bicycle sharing problem that have an exponential complexity. But that does not mean that no fast solution method exist! It just means that we have not yet discovered any fast method yet!

The ‘P versus NP problem’ is exactly that question: can a problem always be solved ‘quickly’ if one can quickly verify that a proposed solution is correct? The P versus NP problem is unsolved, although the question was asked in a very precise mathematical form back in 1971. The person who comes up with a proof (whether the answer is ‘yes’ or ‘no’) can be rewarded with a Millennium Prize of $1,000,000 from the Clay Mathematics Institute.

It has to be said that it is not entirely clear to everyone what the practical impact of the evidence would be: if the answer is ‘yes’, we don’t necessarily have a good algorithm right away, just the certainty that an algorithm must exist. Moreover, it might be safe to assume that the algorithm is theoretically in the ‘P’ class, but that the (constant) speed at which work grows when doubling problem size is so big that for large problems it is still infeasible to calculate the exact solution with that ‘fast’ method.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.